package com.wang.violentrecursion;

/**
 * @Author: along
 * @Create: 2021/4/25
 * @Description:汉诺塔移动问题(n层汉诺塔最优移动步数2^n - 1步)
 */
public class Demo01_Hanoi {
    public static void hanoi1(int n) {
        leftToRight(n);
    }
    public static void leftToRight(int n) {
        if(n == 1) {
            System.out.println("Move 1 from left to right");
            return;
        }
        leftToMid(n - 1);
        System.out.println("Move " + n + "from left to right");
        midToRight(n - 1);
    }
    public static void leftToMid(int n) {
        if(n == 1) {
            System.out.println("Move 1 from left to mid");
            return;
        }
        leftToRight(n - 1);
        System.out.println("Move " + n + "from left to mid");
        rightToMid(n - 1);
    }
    public static void rightToMid(int n) {
        if(n == 1) {
            System.out.println("Move 1 from right to mid");
            return;
        }
        rightToLeft(n - 1);
        System.out.println("Move " + n + "from right to left");
        leftToMid(n - 1);
    }
    public static void midToRight(int n) {
        if(n == 1) {
            System.out.println("Move 1 from mid to right");
            return;
        }
        midToLeft(n - 1);
        System.out.println("Move " + n + "from mid to right");
        leftToRight(n - 1);
    }
    public static void rightToLeft(int n) {
        if(n == 1) {
            System.out.println("Move 1 from right to left");
            return;
        }
        rightToMid(n - 1);
        System.out.println("Move " + n + "from right to left");
        midToLeft(n - 1);
    }
    public static void midToLeft(int n) {
        if(n == 1) {
            System.out.println("Move 1 from mid to left");
            return;
        }
        midToRight(n - 1);
        System.out.println("Move " + n + "from mid to left");
        rightToLeft(n - 1);
    }
    //1~i圆盘  目标是from - to other是另外一个 不用考虑左中右
    public static void hanoi2(int n) {
        if(n > 0) {
            func(n, "left", "right", "mid");
        }
    }
    public static void func(int N, String from, String to, String other) {
        if(N == 1) {//base case
            System.out.println("Move 1 from " + from + " to " + to );
        }
        else {
            func(N -1, from, other, to);
            System.out.println("Move " + N + " from " + from + " to " + to);
            func(N - 1, other, to, from);
        }

    }

    public static void main(String[] args) {
        int n = 3;
        hanoi1(n);
        System.out.println("===========分隔符===========");
        hanoi2(n);
        System.out.println("===========分隔符===========");
    }
}
